package com.jack.leetcode.eachProblem07;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

public class 判断二分图 {

    public boolean isBipartite(int[][] graph) {
        int[] visit = new int[graph.length];
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < graph.length; i++) {
            if (visit[i] != 0) {
                continue;
            }
            queue.offer(i);
            visit[i] = 1;
            while (!queue.isEmpty()) {
                Integer rol = queue.poll();
                for (int v : graph[rol]) {
                    if (visit[v] == visit[rol]) {
                        return false;
                    }
                    if (visit[v] == 0) {
                        visit[v] = -visit[rol];
                        queue.offer(v);
                    }
                }
            }
        }
        return true;
    }
}
